#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
ListNode* CreatNode(float coef, int expn)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->coef = coef;
	node->expn = expn;
	node->next = NULL;
	node->prev = NULL;
	return node;
}
void InitList(List* lt)
{
	assert(lt);
	ListNode** head = &(lt->head);
	*head = CreatNode(0, 0);
	(*head)->next = *head;
	(*head)->prev = *head;
}
int cmp(ListNode* ta, ListNode* tb)
{
	return ta->expn - tb->expn;
}
void Push(ListNode* head, float coef, int expn)
{
	
	if (head->next == head)
		Insert(head->prev, coef, expn);
	else if (head->next->expn == expn)
		head->next->coef += coef;
	else
	{
		ListNode* tmp = head->next;
		ListNode* ctmp = CreatNode(coef, expn);
		while (tmp != head && cmp(tmp,ctmp) < 0 )
		{
			tmp = tmp->next;
		}
		if (cmp(tmp, ctmp) == 0)
		{
			tmp->coef += coef;
			if (tmp->coef == 0)
			{
				DeletePop(tmp);
			}
		}
		else
		{
			Insert(tmp->prev, coef, expn);
		}
		free(ctmp);
	}
}
void Insert(ListNode* node, float coef, int expn)
{
	assert(node != NULL);
	ListNode* tmp = CreatNode(coef, expn);
	tmp->next = node->next;
	node->next = tmp;
	tmp->next->prev = tmp;
	tmp->prev = node;
}
void DeletePop(ListNode* node)
{
	assert(node);
	node->prev->next = node->next;
	node->next->prev = node->prev;
	free(node);
}
void Print(ListNode* head)
{
	assert(head);
	if (Empty(head)) return;
	ListNode* tmp = head->next;
	if (tmp->coef < 0) printf("-");
	while (tmp->next != head)
	{
		printf("(%.2f*x^%d) %c ", (tmp->coef > 0 ? tmp->coef : -tmp->coef), tmp->expn,(tmp->next->coef > 0 ? '+' : '-'));
		
		tmp = tmp->next;
	}
	printf("(%.2f*x^%d)", (tmp->coef > 0 ? tmp->coef : -tmp->coef), tmp->expn);
	printf("\n");
}

int Empty(ListNode* head)
{
	assert(head != NULL);
	return head->next == head;
}

void Destroy(List* lt)
{
	assert(lt);
	assert(lt->head);
	ListNode* tmp = lt->head->next;
	while (tmp->next != lt->head)
	{
		ListNode* node = tmp->next;
		DeletePop(tmp);

		tmp = node;
	}
	free(tmp);
}

int PolyLength(List* lt)
{
	assert(lt);
	assert(lt->head);
	int cnt = 0;
	ListNode* tmp = lt->head->next;
	while (tmp != lt->head)
	{
		cnt++;
		tmp = tmp->next;
	}
	return cnt;
}

void AddList(List* a, List* b)
{
	ListNode* ta = a->head->next;
	ListNode* tb = b->head->next;
	
	while (tb != b->head)
	{
		Push(a->head, tb->coef, tb->expn);
		tb = tb->next;
	}
	Destroy(b);
}


void SubtractList(List* a, List* b)
{
	ListNode* tmp = b->head->next;
	while (tmp != b->head)
	{
		tmp->coef *= -1;
		tmp = tmp->next;
	}
	AddList(a, b);
}


void CreatList(List* lt,int m)
{
	assert(lt);
	assert(lt->head);
	int coef = 0;
	int expn = 0;
	while (m--)
	{
		scanf("%d %d", &coef, &expn);
		Push(lt->head, coef, expn);
	}
}

void MultiOne(List* a, ListNode* node)
{
	ListNode* head = a->head->next;
	while (head != a->head)
	{
		head->coef *= node->coef;
		head->expn += node->expn;
		head = head->next;
	}
}

void Multi(List* a, List* b)
{
	assert(a && b);

	ListNode* ha = a->head->next;
	ListNode* hb = b->head->next;
	List cur = { 0 };
	InitList(&cur);
	while (ha != a->head)
	{
		Push(cur.head, ha->coef, ha->expn);
		ha = ha->next;
	}
	MultiOne(a, hb);
	hb = hb->next;
		while (hb != b->head)
		{
			List tmp = { 0 };
			InitList(&tmp);
			ListNode* ht = tmp.head;
			ListNode* hc = cur.head->next;
			while ( hc != cur.head)
			{
				Push(ht, hc->coef, hc->expn);
				hc = hc->next;
			}

			MultiOne(&tmp, hb);
			hb = hb->next;
			AddList(a, &tmp);
		}
		Destroy(&cur);
}

//if (ha == a->head || hb == b->head)
//{
//	while (ha != a->head)
//	{
//		DeletePop(ha);
//		ha = ha->next;
//	}
//}